Perfect matchings in highly cyclically connected regular graphs
Edita Rollová


Abstract
Plesnik's theorem suggests that every $d$-regular (cyclically) $(d-1)$-edge connected graph has a perfect matching that avoids at most $d-1$ edges. We present a new result that if we increase the cyclic connectivity by $2k$ as compared to the result of Plesnik, we are able to avoid $k$ additional edges unless any of two obvious constraints occurs. Using this result we are able to prescribe one of three paths to be in a $2$-factor of a cubic cyclically $k$-edge-connected graph.  We present a similar statement for two paths when $k=3$ and $k=4$. As a corollary we show that given a vertex $v$ in a cyclically $7$-edge-connected cubic graph, there is a $2$-factor such that $v$ is in a circuit of length greater than $7$. This is a joint work with Robert Lukotka from Comenius university in Bratislava.